package others;

public class Test0ffer26 {
    /**
     * 剑指 Offer 26. 树的子结构
     */
    public class TreeNode {
        String val;
        TreeNode left;
        TreeNode right;

        TreeNode(String x) {
            val = x;
        }
    }

    //判断B是否存在A中
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        //当 树 AA 为空 或 树 BB 为空 时，直接返回 false ；
        if (B == null || A == null) {
            return false;
        }
        //若树 B 是树 A 的子结构 贼需要满足
        //1.以 节点 A 为根节点的子树 包含树 B ，对应 recur(A, B)；
        //2.树 B 是 树 A 左子树 的子结构
        //3.树 B 是 树 A 右子树 的子结构
        return isSubStructure(A.left, B) || isSubStructure(A.right, B) || helper(A,B);
    }

    private boolean helper(TreeNode root1, TreeNode root2) {

        //当节点 root2 为空：说明树 root2 已匹配完成（越过叶子节点），因此返回 truetrue
        if (root2 == null) {
            return true;
        }
        //当节点 root1 为空：说明已经越过树 root1 叶子节点，即匹配失败，返回 falsefalse ；
        if (root1 == null) {
            return false;
        }
        //当节点 root1 和 root2 的值不同：说明匹配失败，返回 falsefalse ； 否则继续递归  且条件为与 b得左子树要在A中 同时右子树也要在A中。
        if (root1.val == root2.val) {
            return helper(root1.left, root2.left) && helper(root1.right, root2.right);
        } else {
            return false;
        }
    }
}
